Focused on the issue that the precise segmentation of remote sensing images which contain complex textures is always difficult, a novel algorithm which combined remote sensing image segmentation with texture removal was proposed. Firstly, the method of texture removal with relative total variation was improved. A new norm constraint was introduced to the relative total variation algorithm, which helped to enhance the major structures in images while removing textures. Meanwhile, the improved texture removal method could assist the following image segmentation. Secondly, mean shift algorithm was used to segment remote sensing images after texture removal by unsupervised clustering. The proposed segmentation algorithm of remote sensing images was tested on different remote sensing images. The experimental results demonstrate that the proposed method can split the main objects from very high resolution remote sensing images. The proposed method obtains better results compared with other methods of remote sensing image segmentation which segmented images without texture removal or segmented remote sensing images combined with other texture removal methods. The proposed method can reduce the influence of texture on image segmentation and improve the accuracy of remote sensing image segmentation.